import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


//官方题解，使用双指针，前一个指针比后一个领先n+1个结点
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode pNodeF = dummy, pNodeB = dummy;
        for(int i = 0; i < n + 1; i++){
            pNodeF = pNodeF.next;
        }
        while(pNodeF != null){
            pNodeF = pNodeF.next;
            pNodeB = pNodeB.next;
        }
        pNodeB.next = pNodeB.next.next;
        return dummy.next;
    }
}


//使用队列
class Solution1 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        LinkedList<ListNode> queue = new LinkedList<>();
        ListNode pHead = new ListNode(0, head);
        ListNode pNode = pHead;
        while(pNode != null){
            queue.addLast(pNode);
            if(queue.size() > n + 1){
                queue.removeFirst();
            }
            pNode = pNode.next;
        }
        ListNode prev = queue.getFirst();
        ListNode next = prev.next.next;
        prev.next = next;
        return pHead.next;
    }
}